package org.usmile.algorithms.leetcode.hard;

/**
 * 327. 区间和的个数
 *
 * 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
 * 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
 *
 * 示例 1：
 * 输入：nums = [-2,5,-1], lower = -2, upper = 2
 * 输出：3
 * 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
 *
 * 示例 2：
 * 输入：nums = [0], lower = 0, upper = 0
 * 输出：1
 *
 * 提示：
 * 1 <= nums.length <= 105
 * -231 <= nums[i] <= 231 - 1
 * -105 <= lower <= upper <= 105
 * 题目数据保证答案是一个 32 位 的整数
 */
public class _0327 {
}

class _0327_Solution {
    private long[] prefixSum;
    int count;
    int lower;
    int upper;

    public int countRangeSum(int[] nums, int lower, int upper) {
        prefixSum = new long[nums.length + 1];
        prefixSum[0] = 0;
        count = 0;
        this.lower = lower;
        this.upper = upper;

        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        mergeSort(0, prefixSum.length - 1);

        return count;
    }

    private void mergeSort(int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;

        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        // 计算当前有效的区间和个数
        int i = left;
        int l = mid + 1;
        int u = mid + 1;
        while (i <= mid) {
            while (l <= right && prefixSum[l] - prefixSum[i] < lower) {
                l++;
            }
            while (u <= right && prefixSum[u] - prefixSum[i] <= upper) {
                u++;
            }
            count += (u - l);
            i++;
        }

        merge(left, mid, right);
    }

    private void merge(int left, int mid, int right) {
        long[] temp = new long[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (k < temp.length) {
            if (i == mid + 1) {
                temp[k++] = prefixSum[j++];
            } else if (j == right + 1) {
                temp[k++] = prefixSum[i++];
            } else if (prefixSum[i] <= prefixSum[j]) {
                temp[k++] = prefixSum[i++];
            } else {
                temp[k++] = prefixSum[j++];
            }
        }

        for (k = 0; k < temp.length; k++) {
            prefixSum[left++] = temp[k];
        }
    }
}